package code.bitmap;

public class BitMap {
    private byte[] bytes;

    // num/8 得到byte[]的index
    public int getIndex(int num) {
        return num / 8; // num >> 3
    }

    public BitMap(int capacity) {
        bytes = new byte[getIndex(capacity)+1];
    }

    // num%8得到在byte[index]的位置
    public int getPosition(int num) {
        return num % 8; // num & 0x07
    }

    // 标记val在bitmap的值，标记其已经出现过
    public void add(int val) {
        bytes[getIndex(val)] |= 1 << getPosition(val);
    }

    public boolean contains(int val) {
        int temp = bytes[getIndex(val)] & 1 << getPosition(val);
        return !(temp == 0);
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(100);
        bitMap.add(1);
        bitMap.add(10);
        bitMap.add(77);
        System.out.println(bitMap.contains(1));
        System.out.println(bitMap.contains(10));
        System.out.println(bitMap.contains(77));
        System.out.println(bitMap.contains(88));
    }
}
